/**
 * 面试题42：连续子数组的最大和
 */
public class Offer_42 {
    /**
     * 方法三：动态规划-空间优化
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int maxSubArray(int[] nums) {
        // 结果
        int ans = nums[0];
        // 当前最大连续子序列和
        int sum = 0;

        /**
         * 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
         * 
         * 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
         * 
         * 每次比较 sum 和 ans 的大小，将最大值置为 ans，遍历结束返回结果
         */
        for (int i = 0; i < nums.length; i++) {
            if (sum > 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }

    /**
     * 方法二：动态规划
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int maxSubArray2(int[] nums) {
        int len = nums.length;
        // dp[i] 表示以元素 nums[i] 为结尾的连续子数组最大和
        int[] dp = new int[len];
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                // 若 dp[i-1] <= 0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，
                // 即 dp[i-1] + nums[i] 还不如 nums[i] 本身大
                dp[i] = nums[i];
            }
            // dp 列表中的最大值，代表全局最大值
            ans = dp[i] > ans ? dp[i] : ans;
        }
        return ans;
    }

    /**
     * 方法一：暴力法（超时）
     * <p>
     * 时间复杂度：O(n^2)
     * <p>
     * 空间复杂度：O(1)
     */
    public int maxSubArray1(int[] nums) {
        int len = nums.length;
        int ans = nums[0];
        for (int i = 0; i < len; i++) {
            int thisSum = 0;
            for (int j = i; j < len; j++) {
                thisSum += nums[j];
                if (thisSum > ans) {
                    ans = thisSum;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Offer_42 solution = new Offer_42();
        int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int ans = solution.maxSubArray(nums);
        System.out.println(ans);
    }
}
